Entropy coding has been studied for decades. Basically, there are three kinds of entropy coding methods: variable length coding (VLC), like Huffman coding, arithmetic coding, and dictionary-based compression, like Lempel-Ziv compression or Lempel-Ziv-Welch compression. The VLC codes use integer number of bits to represent each symbol. Huffman coding is the most widely used VLC method. It assigns fewer bits to the symbol with greater probability, while assigning more bits to the symbol with smaller probability. However, Huffman code cannot be optimal unless the probability of each symbol is an integer power of ½. On the contrary, arithmetic coding can allocate fractional bits to each symbol so that it can approach better the entropy of a group of data. Huffman code and arithmetic code have been widely used in the existing image/video compression standards, e.g., JPEG, MPEG-2, H.264/AVC. The Lempel-Ziv (LZ) or Lempel-Ziv-Welch (LZW) utilize a table-based compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier input data. The algorithm is designed to be fast to implement but is not usually optimal because it performs only limited analysis of the data. This category of algorithms has been employed in GIF, Zip, PNG and some other standards.
In 3D mesh coding, the geometry data is usually compressed by spatial tree based approaches, e.g. kd-tree based [OG00] or octree based [PK05]. These algorithms organize the input spatial points by some spatial tree. Then they traverse the tree structure and record the necessary information for later restoring the input points. While building the spatial tree, a cell is recursively subdivided until each nonempty cell is small enough to contain only one vertex and enable a sufficiently precise reconstruction of the vertex position. Initially, a bounding box is constructed around all points of a 3D model. The entire bounding box of all 3D points is regarded as a single cell in the beginning. As the vertex positions can be restored from the bounding box of the corresponding cells, the spatial tree based algorithms include that they can achieve multi-resolution compression and the same compression ratio as single-resolution compression algorithms.
With each iteration, [OG00] subdivides a cell into two child cells and encodes the number of vertices in one of the two child cells, as shown in FIG. 1. If a parent cell contains p vertices, the number of vertices in one of the child cells can be encoded using log2 (p+1) bits with an arithmetic coder.
On the other hand, [PK05] subdivides in each iteration a non-empty cell into eight child cells. For each octree cell subdivision, the geometry coder encodes the number T (1≦T≦8), of non-empty child cells and the configuration of non-empty child cells among KT=C8T possible combinations. When the data is encoded straight forwardly, T takes 3 bits and the non-empty child cell configuration takes log2 KT bits. To improve coding efficiency, [PK05] estimates for each child cell the pseudo-probability of being not empty. The traversal order of child cells is adapted according to a probability descending order. For the ease of illustration, a 2D example resulting in quadtree child cells, and resulting code words, are shown in FIG. 2. The traversal orders are denoted by arrows.
However, it is always desirable to improve compression in order to achieve a higher compression ratio. It is particularly desirable to achieve this without data loss, i.e. a method that allows a full-quality decompression, resulting in a (quasi-) lossless reproduction.